{\rtf1\ansi\deff0\adeflang1025
{\fonttbl{\f0\froman\fprq2\fcharset128 Times New Roman;}{\f1\froman\fprq2\fcharset128 Times New Roman;}{\f2\fswiss\fprq2\fcharset128 Arial;}{\f3\fnil\fprq0\fcharset128 OpenSymbol{\*\falt Arial Unicode MS};}{\f4\fnil\fprq2\fcharset128 DejaVu Sans;}}
{\colortbl;\red0\green0\blue0;\red128\green128\blue128;}
{\stylesheet{\s1\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033\snext1 Normal;}
{\s2\sb240\sa120\keepn\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\afs28\lang255\ltrch\dbch\langfe255\hich\f2\fs28\lang1033\loch\f2\fs28\lang1033\sbasedon1\snext3 Heading;}
{\s3\sa120\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033\sbasedon1\snext3 Body Text;}
{\s4\sa120\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033\sbasedon3\snext4 List;}
{\s5\sb120\sa120\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\af4\afs24\lang255\ai\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\i\loch\f0\fs24\lang1033\i\sbasedon1\snext5 caption;}
{\s6\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033\sbasedon1\snext6 Index;}
{\s7\sb240\sa120\keepn\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\afs32\lang255\ab\ltrch\dbch\langfe255\hich\f2\fs32\lang1033\b\loch\f2\fs32\lang1033\b\sbasedon2\snext3{\*\soutlvl0} heading 1;}
{\s8\sb240\sa120\keepn\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\afs28\lang255\ai\ab\ltrch\dbch\langfe255\hich\f2\fs28\lang1033\i\b\loch\f2\fs28\lang1033\i\b\sbasedon2\snext3{\*\soutlvl1} heading 2;}
{\s9\sb240\sa120\keepn\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\rtlch\afs28\lang255\ab\ltrch\dbch\langfe255\hich\f2\fs28\lang1033\b\loch\f2\fs28\lang1033\b\sbasedon2\snext3{\*\soutlvl2} heading 3;}
{\*\cs11\cf0\rtlch\af3\afs24\lang255\ltrch\dbch\af3\langfe255\hich\f3\fs24\lang1033\loch\f3\fs24\lang1033 Bullet Symbols;}
}{\*\listtable{\list\listtemplateid1
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u8226 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li360}
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u9702 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li720}
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u9642 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li1080}
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u8226 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li1440}
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u9702 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li1800}
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u9642 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li2160}
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u8226 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li2520}
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u9702 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li2880}
{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u9642 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li3240}
{\*\soutlvl{\listlevel\levelnfc23\leveljc0\levelstartat1\levelfollow0{\leveltext \'01\u8226 ?;}{\levelnumbers;}\f3\f3\f3\f3\fi-360\li3600}}\listid1}
}{\listoverridetable{\listoverride\listid1\listoverridecount0\ls0}}

{\info{\creatim\yr2009\mo5\dy15\hr18\min40}{\revtim\yr0\mo0\dy0\hr0\min0}{\printim\yr0\mo0\dy0\hr0\min0}{\comment StarWriter}{\vern3100}}\deftab709
{\*\pgdsctbl
{\pgdsc0\pgdscuse195\pgwsxn12240\pghsxn15840\marglsxn1134\margrsxn1134\margtsxn1134\margbsxn1134\pgdscnxt0 Standard;}}
\paperh15840\paperw12240\margl1134\margr1134\margt1134\margb1134\sectd\sbknone\pgwsxn12240\pghsxn15840\marglsxn1134\margrsxn1134\margtsxn1134\margbsxn1134\ftnbj\ftnstart1\ftnrstcont\ftnnar\aenddoc\aftnrstcont\aftnstart1\aftnnrlc
\pard\plain \li0\ri0\lin0\rin0\fi-432\sb240\sa120\keepn\f2\fs32\b\fs32\b\fs32\b\qc \ltrpar\s7\cf0\qc{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\li0\ri0\lin0\rin0\fi-432\sb240\sa120\keepn\rtlch\afs32\lang255\ab\ltrch\dbch\langfe255\hich\f2\fs32\lang1033\b\loch\f2\fs32\lang1033\b {\rtlch \ltrch\loch\f2\fs32\lang1033\i0\b Parallelizing Dijkstra's Algorithm using MPI}
\par \pard\plain \ltrpar\s3\cf0\qc{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b0 Jesse Phillips and Peter Nordquist}
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ab\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\b\loch\f0\fs24\lang1033\b{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b Dijkstra's Algorithm:}
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b0 Dijkstra's Algorithm finds the shortest path to all points from a single node. Each node visits it's adjacent nodes assigning a weight if lower than previous traversals to that node. }
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ab\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\b\loch\f0\fs24\lang1033\b{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b MPI Implementation:}
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b0 This implementation is to find the shortest path of a graph using multiple processors communicating with message passing. Each processor will receive a collection of points, their weights and connections, and if the node continues on another processor. }
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b0 Since Dijkstra's progresses from a single location and is solved by traversing from one node to another there is a good chance that there will not be a performance increase from using multiple processors.}
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033
\par \pard\plain {\listtext\pard\plain \li360\ri0\lin360\rin0\fi-360\sa120\f3\f3\f3 \'95\tab}\ilvl0 \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\ls0\li360\ri0\lin360\rin0\fi-360\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b0 Each processor must wait to be told the weight of one of its nodes before it can start processing connected nodes}
\par \pard\plain {\listtext\pard\plain \li360\ri0\lin360\rin0\fi-360\sa120\f3\f3\f3 \'95\tab}\ilvl0 \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b0 The nodes owned by a process may have little connectivity causing a juggle between processors.}
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033
\par \pard\plain \ltrpar\s3\cf0{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\sa120\rtlch\af4\afs24\lang255\ltrch\dbch\af4\langfe255\hich\f0\fs24\lang1033\loch\f0\fs24\lang1033{\rtlch \ltrch\loch\f0\fs24\lang1033\i0\b0 We have decided to leave these issues unresolved and will concentrate on communication.}
\par }